package com.sunny.l5;
public class Solution {

//    public static void main(String[] args) {
//
//        ListNode node1 = new ListNode(1);
//        ListNode node2 = new ListNode(1);
////        ListNode node3 = new ListNode(8);
////        ListNode node4 = new ListNode(5);
////        ListNode node5 = new ListNode(6);
//
//        node1.next = node2;
////        node2.next = node3;
////        node3.next = node4;
////        node4.next = node5;
//
//        Solution solution = new Solution();
//        ListNode res = solution.insertionSortList(node1);
//        solution.print(res);
//
//    }
//    public void print(ListNode head){
//
//        ListNode p = head;
//        while (null != p){
//            System.out.println(p.val);
//            p = p.next;
//        }
//    }



    public ListNode insertionSortList(ListNode head) {

        if(null == head)
            return head;

        int len = getLen(head);

        ListNode p = head.next;
        head.next = null;

        int cnt = 1;
        while (cnt++ < len && null != p){

            ListNode tmpp = p.next;
            head = insertCore(head,p);
            p = tmpp;

        }

        return head;

    }

    public int getLen(ListNode head){

        int res = 0;
        ListNode p = head;
        while (null != p){
            res++;
            p = p.next;
        }
        return res;
    }

    public ListNode insertCore(ListNode head, ListNode node){

        int val = node.val;
        ListNode p = head;

        ListNode tmpPre = null;
        if(p.val > node.val){
            node.next = head;
            head = node;
            return head;
        }

        while (null != p){

            if(p.val > node.val)
                break;

            tmpPre = p;
            p = p.next;
        }

        node.next = tmpPre.next;
        tmpPre.next = node;
        return head;

    }

}

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
      val = x;
      next = null;
    }
 }
